'''
https://leetcode.cn/problems/minimum-cost-to-connect-sticks/
'''
import heapq
from typing import List


class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        heapq.heapify(sticks)
        cost = 0
        while len(sticks) > 1:
            new_stick = heapq.heappop(sticks) + sticks[0]
            cost += new_stick
            heapq.heapreplace(sticks, new_stick)
        return cost